

/*
问题定义：
数组中任意一个连续的长度大于0的片段称之为数组
的一个子数组。数组中所有数字之和称为数字和。
要求：
输入：一个非空数组
输出：所有子数组中数字和最大的那一个。有多个
子数组的数字和同时为最大值时，只取其中之一。
*/

// 生成随机数组
function gen_random_list(start, end, length) { 
    var random_list = []
    for (var i = 0; i < length; i++) {
  	    random_list.push(Math.random() * (end - start) + start)
    }
    return random_list
}
  

// 1: 用暴力方法求解最大子数组问题
function find_maximum_subarray_1(arr) {
    let sum_record = -Infinity
    let left_record = 0
    let right_record = 0
    for (let left = 0; left < arr.length; left++) {
        let sum = 0
        for (let right = left + 1; right < arr.length + 1; right++) {
            sum = sum + arr[right - 1]
            if (sum > sum_record) {
                sum_record = sum
                left_record = left
                right_record = right
            }
        }
    }
    return [left_record, right_record, sum_record]
}

// --- 2: 分治法求最大子数组 ---

// 
function find_max_crossing_subarray(arr, low, mid, high) {
    let left_sum = -Infinity
    let sum = 0
    let max_left = 0
    for (let i = mid; i >= low; i--) {
        sum = sum + arr[i]
        if (sum > left_sum) {
            left_sum = sum
            max_left = i
        }
    }
    let right_sum = -Infinity
    sum = 0
    let max_right = 0
    for (let j = mid + 1; j <= high; j++) {
        sum = sum + arr[j]
        if (sum > right_sum) {
            right_sum = sum
            max_right = j
        }
    }
    return [max_left, max_right, left_sum + right_sum]
}


function find_maximum_subarray_21(arr, low, high) {
    if (high == low)
        return [low, high, arr[low]]
    else {
        let mid = Math.floor((low + high) / 2)
        let res = find_maximum_subarray_21(arr, low, mid)
        let left_low = res[0], left_high = res[1], left_sum = res[2]
        res = find_maximum_subarray_21(arr, mid + 1, high)
        let right_low = res[0], right_high = res[1], right_sum = res[2]
        res = find_max_crossing_subarray(arr, low, mid, high)
        let cross_low = res[0], cross_high = res[1], cross_sum = res[2]
        if (left_sum >= right_sum && left_sum >= cross_sum)
            return [left_low, left_high, left_sum]
        else if (right_sum >= left_sum && right_sum >= cross_sum)
            return [right_low, right_high, right_sum]
        else
            return [cross_low, cross_high, cross_sum]
    }
}


function find_maximum_subarray_2(arr) {
    let res = find_maximum_subarray_21(arr, 0, arr.length - 1)
    let low = res[0], high = res[1], sum = res[2]
    return [low, high + 1, sum]
}

// --- 分治法求解最大子数组结束 ---


// 3: 一种线性时间内求解最大子数组的方法
function find_maximum_subarray_3(arr) {
    let max_sum = -Infinity
    let max_start = 0
    let max_end = 0
    let max_sum_right = -Infinity
    let max_start_right = 0
    let max_end_right = 0
    let sum = 0
    for (let i = 1; i <= arr.length; i++) {
        let value = arr[i - 1]
        if (max_sum_right < 0) {
            max_sum_right = value
            max_start_right = i - 1
            max_end_right = i
        }
        else {
            max_sum_right = max_sum_right + value
            max_end_right = i
        }
        if (max_sum_right > max_sum) {
            max_sum = max_sum_right
            max_start = max_start_right
            max_end = max_end_right
        }
    }
    return [max_start, max_end, max_sum]
}

function main() {
    let list_n = []
    let list_t_0 = []
    let list_t_1 = []
    let list_t_2 = []
    const legend = ['直接计算', '分治法', '一种线性时间内求解的方法']
    for (let i = 1; i <= 6000; i += 20) {
        list_n.push(i)
        let arr = gen_random_list(-1, 1, i)
        let time0 = new Date()
        let res = find_maximum_subarray_1(arr)
        let l1 = res[0], r1 = res[1], s1 = res[2]
        let time1 = new Date()
        list_t_0.push(time1 - time0)
        let time2 = new Date()
        res = find_maximum_subarray_2(arr)
        let l2 = res[0], r2 = res[1], s2 = res[2]
        let time3 = new Date()
        list_t_1.push(time3 - time2)
        let time4 = new Date()
        res = find_maximum_subarray_3(arr)
        let l3 = res[0], r3 = res[1], s3 = res[2]
        let time5 = new Date()
        list_t_2.push(time5 - time4)
        console.assert(Math.abs(s1 - s2) < 1e-8)
        console.assert(Math.abs(s3 - s2) < 1e-8)
    }
    let board = getBoard()
    let p = new Figure(board)
    p.plot(list_n, list_t_0, {color: 'green'})
    p.plot(list_n, list_t_1, {color: 'blue'})
    p.plot(list_n, list_t_2, {color: 'red'})
    console.log("complete")
}


main()
		
